package test.com.codingmanage.sort;

import org.junit.Test;

public class InsertSortArray {
	int[] arr = { 11, 29, 31, 2, 14, 19, 10, 1, 3, 4, 5, 6 };
	int n = arr.length;

	// 三、插入排序
	// --------------------------------------------Code
	// 从小到大排序n个数-------------------------------------
	@Test
	public void InsertSortArray() {
		ArrayPrint.printArr(arr);
		for (int i = 1; i < n; i++)// 循环从第二个数组元素开始，因为arr[0]作为最初已排序部分
		{
			int temp = arr[i];// temp标记为未排序第一个元素
			int j = i - 1;
			while (j >= 0 && arr[j] > temp)/* 将temp与已排序元素从小到大比较，寻找temp应插入的位置 */
			{
				arr[j + 1] = arr[j];
				j--;
			}
			arr[j + 1] = temp;
		}

		System.out.println("\n排序后：");
		ArrayPrint.printArr(arr);
	}

	// ------------------------------Code--------------------------------------------------------------
	// 最佳效率O（n）；最糟效率O（n²）与冒泡、选择相同，适用于排序小列表
	// 若列表基本有序，则插入排序比冒泡、选择更有效率。
}
